package Random_Problem.Day_0204;

/**
 * @author zxc
 * @date 2023/02/04 10:00
 **/

import java.util.Arrays;

/**
 * 题目 ：两个球之间的磁力
 * 题目详述 ：
 * 在代号为 C-137 的地球上，Rick 发现如果他将两个球放在他新发明的篮子里，它们之间会形成特殊形式的磁力。
 * Rick 有n个空的篮子，第i个篮子的位置在position[i]，Morty想把m球放到这些篮子里，使得任意两球间最小磁力最大。
 * 已知两个球如果分别位于x和y，那么它们之间的磁力为|x - y|。
 * 给你一个整数数组position和一个整数m，请你返回最大化的最小磁力。
 *
 * 提示：
 * n == position.length
 * 2 <= n <= 10^5
 * 1 <= position[i] <= 10^9
 * 所有position中的整数 互不相同。
 * 2 <= m <= position.length
 *
 */
public class MaxDistance {
    /**
     * 思路 ：
     * 即，n个空篮子其所对应的位置，使用position数组进行保存;
     * 若是想将m个球放入到n个空篮子中 && 要保证任意两球间的最小磁力最大;
     * ===> 即，在某个磁力i下，m个小球是能够放入到n个空篮子中的; 若是将该磁力变为i + 1的话，那么m个小球就不能够放入到n个空篮子中;
     *
     * 解决方法 ：
     * （1）对于position数组进行排序，position[len - 1] - position[0] == 所能够获取的最大磁力;
     * （2）使用二分查找，遍历磁力的取值范围[0 , 最大磁力],去寻找能够保证m个小球放入到n个空篮子中的最大化的最小磁力;
     * （3）同时，定义函数PutNumber来获取 磁力为i时，小球能够放入的空篮子最大数目;
     *
     * @param position
     * @param m
     * @return
     */
    public int maxDistance(int[] position, int m) {
        // 空篮子所在位置数组positive，是顺序不确定的;
        Arrays.sort(position);
        int len = position.length;
        // 获取最大引力
        int num = position[len - 1] - position[0];
        int left = 0;
        int right = num;
        int result = -1;
        while(left <= right){
            // 二分查找，最小磁力
            int mid = (left + right) / 2;
            if(PutNumber(position , mid) >= m){
                left = mid + 1;
                // 即，最小磁力为mid时，满足题目条件 && mid + 1作为最小磁力时，不满足题目条件
                // ===》 即，能够推出mid就为最大化的最小磁力;
                // 注意 : 若是mid满足题目条件的话，则取值范围[0 , mid]作为最小磁力都是能够满足题目条件的
                result = mid;
            }
            else {
                right = mid - 1;
            }
        }
        return result;
    }
    // 判断最小磁力为n时，是否能够将m个球装进n个空篮子中;
    private int PutNumber(int[] position, int gap) {
        // 变量preValue，来保存上一个已经装过球篮子的值;
        int preValue = position[0];
        int len = position.length;
        // sum变量，用来记录 最小磁力为i时，能够向n个空蓝中装入球的总数;
        int sum = 1;
        // 即，遍历所有空篮子,若是 position[i] - preValue >= gap的话，则代表该position[i]是能够装入球的;
        for(int i = 1 ; i < len ; i++){
            if(position[i] - preValue >= gap){
                preValue = position[i];
                sum++;
            }
        }
        return sum;
    }
    /**
     * 核心思想 ：二分查找（精确定位所能够满足要求的最大值）;
     */
}
